// ShortestPath.cpp : Defines the entry point for the console application.
//
/*************************************************************************************************************************************************
/*Author:        Shujun Liu
/*Date:            02/25/2012
/*Version:        1.0
/*Description:    
/*This code is the impletation of a graph that simultaneously finds the shortest 
/*path from a single vertex in a weighted graph to all other vertices in the graph, 
/*called the single-source shortest path problemalgorithm 
/*
/* *********************************************************************************************************************************************
/* ----------------------------------------------------------Algorithm-------------------------------------------------------------------------- 
/*
/* Let the vertex at which we are starting be called the initial vertex. Let the distance of vertex Y be the distance from the initial vertex to Y. 
/* Dijkstra's algorithm will assign some initial distance values and will try to improve them step by step.

/*   1. Assign to every vertex a tentative distance value: set it to zero for our initial vertex and to infinity for all other vertexs.
/*   2. Mark all vertexs unvisited. Set the initial vertex as current. Create a set of the unvisited vertexs called the unvisited set consisting of 
/*      all the vertexs except the initial vertex.
/*   3. For the current vertex, consider all of its unvisited neighbors and calculate their tentative distances. For example, if the current vertex 
/*      A is marked with a tentative distance of 6, and the edge connecting it with a neighbor B has length 2, then the distance to B (through A) 
/*      will be 6+2=8. If this distance is less than the mapPreviously recorded tentative distance of B, then overwrite that distance. Even though a 
/*      neighbor has been examined, it is not marked as visited at this time, and it remains in the unvisited set.
/*   4. When we are done considering all of the neighbors of the current vertex, mark the current vertex as visited and remove it from the unvisited 
/*      set. A visited vertex will never be checked again; its distance recorded now is final and minimal.
/*   5. If the destination vertex has been marked visited (when planning a route between two specific vertexs) or if the smallest tentative distance 
/*      among the vertexs in the unvisited set is infinity (when planning a complete traversal), then stop. The algorithm has finished.
/*   6. Set the unvisited vertex marked with the smallest tentative distance as the next "current vertex" and go back to step 3.
/* 
/***********************************************************************************************************************************************/
#include "stdafx.h"
#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <list>
#include <set>
#include <limits> // for numeric_limits
using namespace std;

typedef int VERTEXID;

struct edge 
{
    const VERTEXID    vertexTarget;
    const double      dWeight;
    edge(VERTEXID id, double dWeight)
        : vertexTarget(id), dWeight(dWeight) 
    {

    }
};

typedef map<VERTEXID, std::list<edge> > MAP_ADJACENCY;

///////////////////////////////////////////////////////////////////////////
// Compute the shortest distance
// source (in): The source vertex from which all shortest paths are found
// adjacency (in): The adjacency map specifying the connection between vertices and edge weights.
// mapMinDistance(out): Will receive the shortest distance from source to each vertex in the graph.
// mapPrevious (out): Receives a map that can be passed back into DijkstraGetShortestPathTo() later on 
//                  to quickly get a shortest path from the source vertex to any desired vertex. 
void DijkstraComputePaths(VERTEXID vertexSource,
                          const MAP_ADJACENCY &adjacency,
                          std::map<VERTEXID, double> &mapMinDistance,
                          std::map<VERTEXID, VERTEXID> &mapPrevious)
{
    //initialize output parameters, set it to zero for our initial vertex and to infinity for all other vertexs
    MAP_ADJACENCY::const_iterator vertex_iter = adjacency.begin();
    for (; vertex_iter != adjacency.end(); vertex_iter++)
    {
        VERTEXID vertex = vertex_iter->first;
        mapMinDistance[vertex] = std::numeric_limits<double>::infinity();

        list<edge>::const_iterator edge_iter = vertex_iter->second.begin();
        for (; edge_iter != vertex_iter->second.end();edge_iter++)
        {
            VERTEXID vNeighbour = edge_iter->vertexTarget;
            mapMinDistance[vNeighbour] = std::numeric_limits<double>::infinity();
        }
    }

    mapMinDistance[vertexSource] = 0;

    //visit each vertex u, always visiting vertex with smallest mapMinDistance first. 
    //Hint!!! data insert into std::set is alway keep ascending order:
    set<pair<double, VERTEXID>> vertex_set;
    vertex_set.insert(make_pair(mapMinDistance[vertexSource], vertexSource));

    while (!vertex_set.empty()) 
    {
        VERTEXID vCur = vertex_set.begin()->second;
        vertex_set.erase(vertex_set.begin());


        // Visit each edge exiting vertex
        const std::list<edge> &edges = adjacency.find(vCur)->second;
        list<edge>::const_iterator edge_iter = edges.begin();
       
        for (; edge_iter != edges.end(); edge_iter++)
        {
            VERTEXID vTarget = edge_iter->vertexTarget;
            
            double dDistance2Target = mapMinDistance[vCur] + edge_iter->dWeight;
            if (dDistance2Target < mapMinDistance[vTarget]) 
            {
                vertex_set.erase(std::make_pair(mapMinDistance[vTarget], vTarget));
                //update the new minmum distance to target.
                mapMinDistance[vTarget] = dDistance2Target;
                mapPrevious[vTarget] = vCur;
                vertex_set.insert(std::make_pair(mapMinDistance[vTarget], vTarget));
            }

        }
    }
}


///////////////////////////////////////////////////////////////////////////
// Get shortest path function
//  
std::list<VERTEXID> DijkstraGetShortestPathTo(VERTEXID target, const map<VERTEXID, VERTEXID> &mapPrevious)
{
    std::list<VERTEXID> path;
    std::map<VERTEXID, VERTEXID>::const_iterator prev;
    VERTEXID vertex = target;
    path.push_front(vertex);
    while((prev = mapPrevious.find(vertex)) != mapPrevious.end())
    {
        vertex = prev->second;
        path.push_front(vertex);
    }
    return path;
}


int _tmain(int argc, _TCHAR* argv[])
{
    MAP_ADJACENCY mapAdjacency;
    std::vector<string> vertex_names;
    //initialize adjacency map
    vertex_names.push_back("Redmond");      // 0
    vertex_names.push_back("Bellevue");     // 1
    vertex_names.push_back("Seattle");      // 2
    vertex_names.push_back("Tacoma");       // 3
    vertex_names.push_back("Bothel");       // 4
    vertex_names.push_back("Kirkland");     // 5
    vertex_names.push_back("Sammamish");    // 6
    mapAdjacency[0].push_back(edge(1, 10.83));
    mapAdjacency[0].push_back(edge(5, 81.15));
    mapAdjacency[1].push_back(edge(0, 10.83));
    mapAdjacency[1].push_back(edge(2, 60.00));
    mapAdjacency[1].push_back(edge(3, 90.75));
    mapAdjacency[1].push_back(edge(5, 99.10));
    mapAdjacency[2].push_back(edge(1, 60.00));
    mapAdjacency[2].push_back(edge(6, 130.89));
    mapAdjacency[2].push_back(edge(3, 20.20));
    mapAdjacency[3].push_back(edge(1, 90.75));
    mapAdjacency[3].push_back(edge(5, 157.30));
    mapAdjacency[3].push_back(edge(6, 89.79));
    mapAdjacency[3].push_back(edge(2, 20.20));
    mapAdjacency[4].push_back(edge(5, 33.04));
    mapAdjacency[4].push_back(edge(6, 140.15));
    mapAdjacency[5].push_back(edge(0, 81.15));
    mapAdjacency[5].push_back(edge(3, 157.30));
    mapAdjacency[5].push_back(edge(4, 33.04));
    mapAdjacency[5].push_back(edge(6, 111.63));
    mapAdjacency[5].push_back(edge(1, 99.10));
    mapAdjacency[6].push_back(edge(2, 130.89));
    mapAdjacency[6].push_back(edge(3, 89.79));
    mapAdjacency[6].push_back(edge(5, 111.63));
    mapAdjacency[6].push_back(edge(4, 140.15));


    map<VERTEXID, double> mapMin_distance;
    std::map<VERTEXID, VERTEXID> mapPrevious;
    DijkstraComputePaths(0, mapAdjacency, mapMin_distance, mapPrevious);
    MAP_ADJACENCY::const_iterator vertex_iter = mapAdjacency.begin();

    for (;vertex_iter!= mapAdjacency.end();vertex_iter++)
    {
        VERTEXID v = vertex_iter->first;
        std::cout << "Distance to " << vertex_names[v] << ": " << mapMin_distance[v] << std::endl;
        std::list<VERTEXID> path = DijkstraGetShortestPathTo(v, mapPrevious);
        std::list<VERTEXID>::const_iterator path_iter = path.begin();
        std::cout << "Path: ";
        for( ; path_iter != path.end(); path_iter++)
        {
            std::cout << vertex_names[*path_iter] << " ";
        }
        std::cout << std::endl;
    }

    getchar();
    return 0;
}

